import datastructure.linklist.ListNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/13 15:34
 * @description:
 */
public class Solution148 {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    // 排序范围：[head, tail)，左闭右开
    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        // 关键终止条件：子链表只有一个节点时，断开连接并返回
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode list1 = sortList(head, slow);
        ListNode list2 = sortList(slow, tail);
        return mergeList(list1, list2);
    }

    ListNode mergeList(ListNode headA, ListNode headB) {
        ListNode dummy = new ListNode(-1);
        ListNode pA = headA, pB = headB;
        ListNode p = dummy;
        while (pA != null && pB != null) {
            if (pA.val < pB.val) {
                p.next = pA;
                pA = pA.next;
            } else {
                p.next = pB;
                pB = pB.next;
            }
            p = p.next;
        }
        if (pA != null) {
            p.next = pA;
        }
        if (pB != null) {
            p.next = pB;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        Solution148 solution = new Solution148();
        ListNode head = ListNode.arrayToList(new int[]{4, 2, 1, 3});
        ListNode newHead = solution.sortList(head);
        ListNode.printList(newHead);
    }
}
